package geek;

import java.util.Stack;

import data_structure.BTNode;

public class Tree_algorithm_day3 {	
	
	
	/**
	 * pre-order: root->left->right
	 * @param root
	 */
	public static void preorderTraversalUsingStack(BTNode root){
		if(root == null) return;
		Stack<BTNode> s = new Stack<BTNode>();
		s.push(root);
		System.out.println();
		while(!s.isEmpty()){
			BTNode node = s.pop();
			System.out.print(node.val);
			if(node.right != null) s.push(node.right);
			if(node.left != null) s.push(node.left);
		}
		System.out.println();
	}
	
	/**
	 * ! in-order: left->root->right
	 * @param root
	 */
	public static void inorderTraversalUsingStack(BTNode root){
		if(root == null) return;
		Stack<BTNode> s = new Stack<BTNode>();
		BTNode current = root;
		s.push(current);
		System.out.println();
		
		while(!s.isEmpty()){
			if(current == null) continue;
			while(current.left != null){
				current = current.left;
				s.push(current);
			}
			current = s.pop();
			System.out.print(current.val+" ");
			current = current.right;
			if(current != null) s.push(current);
		}
		System.out.println();
	}
	
	
	public static void postorderTraversalUsingStack(BTNode root){
		if(root == null) return;
		
	}
	
	/**
	 * 1) Perform standard bst insert new node
	 * 2) Start from the new node, travel up and find the first unbalanced node
	 * 
	 * http://www.geeksforgeeks.org/avl-tree-set-1-insertion/
	 * @param root
	 * @param val
	 */
	public static <T extends Number> void avlTreeInsert(BSTNode<T> root, T val){
		
	}
	
	
	public static <T extends Number> void pairWithSum(BSTNode<T> root){
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
